package com.learn.algorlthm;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @classname:
 * @Description: 字符串的排列
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-08-04 15:29
 * 题目描述：
 * 输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出字符a，b，c所能排列出来的
 * 所有字符串abc,acb,bac,bca,cab和cba。
 */
public class Learn38 {

    private static ArrayList<String> ret = new ArrayList<>();

    public static ArrayList<String> permutation(String str) {
        if (str == null || str.isEmpty())
            return ret;
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        backtracking(chars, new boolean[chars.length], new StringBuilder());
        return ret;
    }

    private static void backtracking(char[] chars, boolean[] booleans, StringBuilder stringBuilder) {

        if (chars.length == stringBuilder.length()) {
            ret.add(stringBuilder.toString());
            return;
        }

        for (int i = 0; i < chars.length; i++) {

            if (booleans[i])
                continue;

            if (i != 0 && chars[i] == chars[i -1] && !booleans[i - 1])
                continue;

            booleans[i] = true;
            stringBuilder.append(chars[i]);
            backtracking(chars, booleans, stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            booleans[i] = false;
        }
    }

}
